package main

import (
	"fmt"
	. "go_data_structures_and_algorithms/system_class/section11/pojo"
	"strconv"
)

//二叉树转字符串先用前序遍历的递归方法

func main() {
	node1 := NewBinaryTree(0) // 根节点
	node2 := NewBinaryTree(1)
	node3 := NewBinaryTree(3)
	node4 := NewBinaryTree(4)
	node5 := NewBinaryTree(5)
	node1.Left = node2
	node1.Right = node3
	node2.Left = node4
	node2.Right = node5

	strings := serialize(node1)

	fmt.Println(strings)

	tree := deserialize(strings)
	fmt.Println(CengJiBianLi(tree))

	i := levelSerialize(tree)
	fmt.Println(i)

	binaryTree := levelDeserialize(i)
	i1 := levelSerialize(binaryTree)
	fmt.Println(i1)

}

// 将二叉树转化成字符串
func serialize(tree *BinaryTree) []string {
	strs := []string{}

	if tree == nil {
		return strs
	}

	preDFS(tree, &strs)

	return strs
}

func preDFS(tree *BinaryTree, strs *[]string) {
	if tree == nil {
		*strs = append(*strs, "#")
		return
	}
	*strs = append(*strs, strconv.Itoa(tree.Value))
	preDFS(tree.Left, strs)
	preDFS(tree.Right, strs)
}

// 将字符串转化成二叉树
func deserialize(strs []string) *BinaryTree {

	if strs == nil || len(strs) == 0 {
		return nil
	}
	queue1 := NewQueue1[string]()
	for _, value := range strs {
		queue1.Offer(value)
	}

	return preDe(queue1)
}

func preDe(strs *Queue1[string]) *BinaryTree {
	if strs.IsEmpty() {
		return nil
	}
	cur := strs.Poll()
	if cur == "#" {
		return nil
	}

	valueint, _ := strconv.Atoi(cur)
	tree := NewBinaryTree(valueint)
	tree.Left = preDe(strs)
	tree.Right = preDe(strs)
	return tree
}

// 层级遍历的序列化
func levelSerialize(tree *BinaryTree) []string {
	strs := []string{}

	if tree == nil {
		return strs
	}

	LevelDFS(tree, &strs)

	return strs
}

func LevelDFS(tree *BinaryTree, strs *[]string) {
	if tree == nil {
		*strs = append(*strs, "#")
		return
	}
	queue1 := NewQueue1[*BinaryTree]()
	queue1.Offer(tree)
	*strs = append(*strs, strconv.Itoa(tree.Value))
	for !queue1.IsEmpty() {
		poll := queue1.Poll()

		if poll.Left != nil {
			//判断完后确认有左节点后直接把左节点的值加入到数组中然后将子节点放入队列中
			*strs = append(*strs, strconv.Itoa(poll.Left.Value))
			//因为队列遵循先进先出的方式所以先放入左节点再放入右节点出来的时候先是左节点再是右节点同理
			//左节点的子节点比右节点的子节点更早进入队列所以更早出来
			queue1.Offer(poll.Left)

		} else { //如果遇到nil直接往字符数组里面放入#占位
			*strs = append(*strs, "#")
		}
		if poll.Right != nil {
			*strs = append(*strs, strconv.Itoa(poll.Right.Value))
			queue1.Offer(poll.Right)

		} else {
			*strs = append(*strs, "#")
		}

	}
}

// 层级遍历的反序列化
func levelDeserialize(strs []string) *BinaryTree {

	if strs == nil || len(strs) == 0 {
		return nil
	}
	queue1 := NewQueue1[string]()
	for _, value := range strs {
		queue1.Offer(value)
	}

	return levelDe(queue1)
}

func levelDe(queue1 *Queue1[string]) *BinaryTree {
	if queue1.IsEmpty() || queue1 == nil {
		return nil
	}

	head := generateBinaryTreeNode(queue1.Poll())
	queue2 := NewQueue1[*BinaryTree]() //需要通过一个额外的栈来实现
	if head != nil {
		queue2.Offer(head)
	}

	for !queue2.IsEmpty() {
		poll := queue2.Poll()
		//因为是层级遍历所以按照顺序从队列中取就完事了然后通过额外的栈来保存对应的父节点
		poll.Left = generateBinaryTreeNode(queue1.Poll())  //将队列里面的内容取出并生成节点返回
		poll.Right = generateBinaryTreeNode(queue1.Poll()) //将队列里面的内容取出并生成节点返回

		if poll.Left != nil {
			queue2.Offer(poll.Left) //如果左节点不为空就保存到额外的栈里面等待下一次取出后挂载节点

		}
		if poll.Right != nil {
			queue2.Offer(poll.Right)

		}
	}

	return head
}

func generateBinaryTreeNode(str string) *BinaryTree { //如果传进来的字符是#就返回nil不然就包装成BinaryTree返回
	if str == "#" {
		return nil
	} else {
		valueint, _ := strconv.Atoi(str)
		tree := NewBinaryTree(valueint)
		return tree
	}

}
